/*
 * Peripheral Simulator (PSim)
 *
 * Copyright (c) 2008 Avadh Patel
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#include <pram.h>

#include <math.h>

#define SECTOR_BITS 9
#define SECTOR_SIZE (1 << SECTOR_BITS)

//User defined PRAM configurations
#define PRAM_SIZE 0x08000000
#define PRAM_BANKS 8
#define PRAM_SET_ASSOC 4
#define PRAM_BLOCK_SIZE SECTOR_SIZE //in bytes

#define PRAM_VB_SIZE 32
#define PRAM_VB_WB_DELTA 1000

//Calculated PRAM configuration
#define PRAM_BANK_SIZE PRAM_SIZE/PRAM_BANKS
#define PRAM_NUM_ROWS PRAM_BANK_SIZE/(PRAM_SET_ASSOC*PRAM_BLOCK_SIZE)

static int pram_row_bits = 0;
static int pram_block_bits = 0;
static int pram_bank_bits = 0;

//PRAM structure that holds all information
static pram_cache_line_t* pram_cache = NULL;

//Victim Buffer structure that holds all information
//static victim_buf_entry_t* victim_buffer = NULL;
static victim_buf_entry_t* vb_root_node = NULL;
static int vb_total_entries = 0;
static uint64_t last_wb_tag = 0;

//Stats counters
static counter_t total_access = 0;
static counter_t read_hit = 0;
static counter_t read_miss = 0;
static counter_t write_hit = 0;
static counter_t write_miss = 0;
static counter_t write_back = 0;
static counter_t pram_size = PRAM_SIZE;
static counter_t pram_banks = PRAM_BANKS;
static counter_t pram_set_assoc = PRAM_SET_ASSOC;
static counter_t pram_block_size = PRAM_BLOCK_SIZE;
static counter_t pram_bank_size = PRAM_BANK_SIZE;
static counter_t vb_access = 0;
static counter_t vb_read_hit = 0;
static counter_t vb_read_miss = 0;
static counter_t vb_write_hit = 0;
static counter_t vb_write_miss = 0;
static counter_t vb_write_back = 0;
static counter_t pram_vb_size = PRAM_VB_SIZE;


void init_pram()
{
    //create the pram module of given size
    pram_cache = qemu_mallocz(sizeof(pram_cache_line_t)*PRAM_BANKS*
            PRAM_NUM_ROWS * PRAM_SET_ASSOC);

    pram_row_bits = (int)(log2((float)PRAM_NUM_ROWS));
    pram_block_bits = (int)(log2((float)PRAM_BLOCK_SIZE));
    pram_bank_bits = (int)(log2((float)PRAM_BANKS));

    //init the victim buffer
    init_victim_buffer();

    //init the stats
    struct stat_sdb_t* sdb = sim_get_stat_db();

    //reigster some constant values as counters, so they are shown in the
    //stats that is generated by the simulator
    stat_reg_const(sdb, "pram.size", "total size of PRAM",
            &pram_size, pram_size, NULL);
    stat_reg_const(sdb, "pram.banks", "total no of banks in PRAM",
            &pram_banks, pram_banks, NULL);
    stat_reg_const(sdb, "pram.set_assoc", "set assoc of PRAM",
            &pram_set_assoc, pram_set_assoc, NULL);
    stat_reg_const(sdb, "pram.block_size", "block size of PRAM",
            &pram_block_size, pram_block_size, NULL);
    stat_reg_const(sdb, "pram.bank_size", "bank size of PRAM",
            &pram_bank_size, pram_bank_size, NULL);
    //now register actual counters
    stat_reg_counter(sdb, "pram.total_access", "total number of PRAM accesses",
            &total_access, 0, NULL);
    stat_reg_counter(sdb, "pram.read_hit", "total number of read hit in PRAM",
            &read_hit, 0, NULL);
    stat_reg_counter(sdb, "pram.read_miss", "total number of read miss in PRAM",
            &read_miss, 0, NULL);
    stat_reg_counter(sdb, "pram.write_hit", "total number of write hit in PRAM",
            &write_hit, 0, NULL);
    stat_reg_counter(sdb, "pram.write_miss", "total number of write miss in PRAM",
            &write_miss, 0, NULL);
    stat_reg_counter(sdb, "pram.write_back", "total number of write back in PRAM",
            &write_back, 0, NULL);

    stat_reg_formula(sdb, "pram.read_hit_ratio", "ratio of read_hit / total_access",
            "pram.read_hit / pram.total_access", NULL);
    stat_reg_formula(sdb, "pram.read_miss_ratio", "ratio of read_miss / total_access",
            "pram.read_miss / pram.total_access", NULL);
    stat_reg_formula(sdb, "pram.write_hit_ratio", "ratio of write_hit/total_access",
            "pram.write_hit / pram.total_access", NULL);
    stat_reg_formula(sdb, "pram.write_miss_ratio", "ratio of write_miss/total_access",
            "pram.write_miss / pram.total_access", NULL);

    stat_reg_const(sdb, "pram.vb.size", "total size of victim buf in PRAM",
            &pram_vb_size, pram_vb_size, NULL);
    stat_reg_counter(sdb, "pram.vb.total_access", "total access of PRAM VB",
            &vb_access, 0, NULL);
    stat_reg_counter(sdb, "pram.vb.read_hit", "total read hit on PRAM VB",
            &vb_read_hit, 0, NULL);
    stat_reg_counter(sdb, "pram.vb.read_miss", "total read miss on PRAM VB",
            &vb_read_miss, 0, NULL);
    stat_reg_counter(sdb, "pram.vb.write_hit", "total write hit on PRAM VB",
            &vb_write_hit, 0, NULL);
    stat_reg_counter(sdb, "pram.vb.write_miss", "total write miss on PRAM VB",
            &vb_write_miss, 0, NULL);
    stat_reg_counter(sdb, "pram.vb.write_back", "total write back from PRAM VB",
            &vb_write_back, 0, NULL);

    //test code
//    access_pram(100, READ_MSG);
//    access_pram(123456789, WRITE_MSG);
//    access_pram(133456789, WRITE_MSG);
//    access_pram(143456789, WRITE_MSG);
//    access_pram(153456789, WRITE_MSG);
//    access_pram(163456789, WRITE_MSG);
//    access_pram(173456789, WRITE_MSG);
//    access_pram(183456789, WRITE_MSG);
//    access_pram(193456789, WRITE_MSG);
//    access_pram(203456789, WRITE_MSG);
//    access_pram(213456789, WRITE_MSG);
//    access_pram(223456789, WRITE_MSG);
//    access_pram(233456789, WRITE_MSG);
//    access_pram(243456789, WRITE_MSG);
//    access_pram(253456789, WRITE_MSG);
//    access_pram(263456789, WRITE_MSG);
//    access_pram(273456789, WRITE_MSG);
//    access_pram(283456789, WRITE_MSG);
//    access_pram(293456789, WRITE_MSG);
//    access_pram(303456789, WRITE_MSG);
//    access_pram(313456789, WRITE_MSG);
//    access_pram(323456789, WRITE_MSG);
//    access_pram(333456789, WRITE_MSG);
//    access_pram(343456789, WRITE_MSG);
//    access_pram(353456789, WRITE_MSG);
//    access_pram(363456789, WRITE_MSG);
//    access_pram(373456789, WRITE_MSG);
//    access_pram(383456789, WRITE_MSG);
//    access_pram(393456789, WRITE_MSG);

}

static int find_bank(uint64_t addr)
{
    //bank is direct mapped
    int pram_bank_low_bit = pram_block_bits + pram_row_bits;
    
    int pram_bank_no = -1;
    pram_bank_no = (addr >> pram_bank_low_bit) & ((int)pow(2, pram_bank_bits) - 1);

    return pram_bank_no;
}

static int find_row(uint64_t addr)
{
    int row_low_bit = pram_block_bits;
    
    int row_no = -1;
    row_no = (addr >> row_low_bit) & ((int)pow(2, pram_row_bits) - 1);

    return row_no;
}

static uint64_t find_tag(uint64_t addr)
{
    return addr >> pram_block_bits;
}

static uint64_t find_addr_from_tag(uint64_t tag)
{
    return tag << pram_block_bits;
}

int find_set(uint64_t addr, int bank, int row)
{
    uint64_t tag = find_tag(addr);//addr >> pram_block_bits;

    int i;
    for(i=0; i<PRAM_SET_ASSOC; i++)
    {
        if(pram_cache[(bank*row)+ i].tag_addr == tag) {
            return i;
        }
    }
    return -1;
}

void update_lru(int bank, int row, int set)
{
    int last_lru = pram_cache[(bank*row) + set].lru_count;
    pram_cache[(bank*row) + set].lru_count = PRAM_SET_ASSOC - 1;
    
    int i;
    for(i=0; i < PRAM_SET_ASSOC; i++) {
        if(pram_cache[(bank*row) + i].lru_count > last_lru && i != set)
            pram_cache[(bank*row) + i].lru_count--;
    }
}

int access_pram(uint64_t addr, uint8_t type)
{
    int bank_no = find_bank(addr);
    int row_no = find_row(addr);

    int set_no = find_set(addr, bank_no, row_no);

    total_access++;

    //If its a hit or not
    if(set_no != -1) {
        update_lru(bank_no, row_no, set_no);
        if(type == WRITE_MSG) {
            pram_cache[(bank_no*row_no) + set_no].modified_flag = 1;
            write_hit++;
        }
        else if(type == READ_MSG) {
            read_hit++;
        }
        return 1;
    }

    //its a miss in main buffer, so check victim buffer
    if(type == WRITE_MSG)
        write_miss++;
    else
        read_miss++;

    //check victim buffer
    victim_buf_entry_t* entry = search_victim_entry(addr);
    if(entry != NULL) {
        //hit in victim buffer
        if(type == WRITE_MSG) {
            vb_write_hit++;
        } else {
            vb_read_hit++;
        }
        return 1;
    }

    //its a miss, set new entry
    set_new_pram_entry(addr, type);
    if(type == WRITE_MSG) {
        vb_write_miss++;
    }
    else if(type == READ_MSG) {
        vb_read_miss++;
    }

    return 0;
}

void access_pram_sector(int64_t sector_num, uint8_t type)
{
    //sector size is fixed
    uint64_t addr = sector_num << SECTOR_BITS;
    access_pram(addr, type);
}

void set_new_pram_entry(uint64_t addr, uint8_t type)
{
    int bank_no = find_bank(addr);
    int row_no = find_row(addr);

    uint64_t tag = find_tag(addr);

    //find set entry with lowest lru count
    int i, lru_set;
    for(i=0; i < PRAM_SET_ASSOC; i++) {
        //first find entry that is unmodified
        if(pram_cache[(bank_no*row_no)+i].modified_flag == 0) {
            lru_set = i;
            break;
        }
        if(pram_cache[(bank_no*row_no) + i].lru_count == 0)
            lru_set = i;
    }

    //now check if the replacement entry is modified or not
    if(pram_cache[(bank_no*row_no) + lru_set].modified_flag == 1) {
        //move this entry to victim buffer to write back to hd
        add_victim_entry(&(pram_cache[(bank_no*row_no) + lru_set]));
        write_back++;
    }

    //set new entry in lru_set
    pram_cache[(bank_no*row_no) + lru_set].tag_addr = tag;
    if(type == WRITE_MSG)
        pram_cache[(bank_no*row_no) + lru_set].modified_flag = 1;
    update_lru(bank_no, row_no, i);

}

void copy_pram_entry(pram_cache_line_t* source, pram_cache_line_t* dest)
{
    dest->tag_addr = source->tag_addr;
    dest->modified_flag = source->modified_flag;
    dest->lru_count = source->lru_count;
}

//Victim Buffer 

void init_victim_buffer()
{
    //victim_buffer = qemu_mallocz(sizeof(victim_buf_entry_t)*PRAM_VB_SIZE);
    vb_root_node = NULL;
}

victim_buf_entry_t* create_new_vb_entry(pram_cache_line_t* pram_entry)
{
    victim_buf_entry_t* node= qemu_mallocz(sizeof(victim_buf_entry_t));
    node->cache_line = qemu_mallocz(sizeof(pram_cache_line_t));
    copy_pram_entry(pram_entry, node->cache_line);
    node->lchild = NULL;
    node->rchild = NULL;
    vb_total_entries++;
    return node;
}

void add_victim_entry(pram_cache_line_t* pram_entry)
{
    vb_access++;
    //check if the buffer is full or not
    if(vb_total_entries >= PRAM_VB_SIZE - (PRAM_VB_SIZE/10)) {
        flush_victim_buffer();
    }
    if(vb_root_node == NULL)  {
        vb_root_node = create_new_vb_entry(pram_entry);
    }
    else {
        victim_buf_entry_t* node1 = vb_root_node;
        while(1) {
            if(node1->cache_line->tag_addr > pram_entry->tag_addr) {
                if(node1->lchild == NULL) {
                    node1->lchild = create_new_vb_entry(pram_entry);
                    return;
                } else {
                    node1 = node1->lchild;
                    continue;
                }
            } else if(node1->cache_line->tag_addr == pram_entry->tag_addr) {
                //node already exsist..
                return;
            } else {
                if(node1->rchild == NULL) {
                    node1->rchild = create_new_vb_entry(pram_entry);
                    return;
                } else {
                    node1 = node1->rchild;
                    continue;
                }
            }
        }
    }
}

victim_buf_entry_t* search_victim_entry_in_range(uint64_t addr1, uint64_t addr2)
{
    uint64_t tag1 = find_tag(addr1);
    uint64_t tag2 = find_tag(addr2);

    victim_buf_entry_t* node = vb_root_node;
    if(node == NULL) {
        return NULL;
    }

    while(1) {
        if(addr1 <= node->cache_line->tag_addr <= addr2) {
            return node;
        } else if(node->cache_line->tag_addr > addr2) {
           if(node->lchild == NULL) {
              return NULL;
           } else {
              node = node->lchild;
           } 
        } else if(node->cache_line->tag_addr < addr1) {
            if(node->rchild == NULL) {
                return NULL;
            } else {
                node = node->rchild;
            }
        }
    }
    return NULL;
}

int flush_nearby_entries(victim_buf_entry_t* entry)
{
    int max_flush_count = PRAM_VB_SIZE/10;
    int flush_count = 0;
    //we start looking in increasing order to flush entries
    //
    victim_buf_entry_t* node = entry;

start_flush:

    while(flush_count < max_flush_count) {
        if(node == NULL) {
            break;
        } else {
           //flush the current node - so mark its modified flags = 0
           node->cache_line->modified_flag = 0;
           last_wb_tag = node->cache_line->tag_addr;
           vb_write_back++;
           flush_count++;
           if(node->rchild == NULL) {
            break;
           } else {
               node = node->rchild;
               continue;
           }
        }
    }

    //At the end check if flush_count is not max then set the starting
    //entry to be the head of the buffer and start flushing
    if(flush_count < max_flush_count) {
        node = vb_root_node;
        goto start_flush;
    }

    return flush_count;
}

void flush_victim_buffer()
{
    uint64_t addr1 = find_addr_from_tag(last_wb_tag);
    uint64_t addr2 = addr1 + PRAM_VB_WB_DELTA;

    victim_buf_entry_t* ent = search_victim_entry_in_range(addr1, addr2);
    int count=0;
    if(ent != NULL) {
        count = flush_nearby_entries(ent);
    } else {
        count = flush_nearby_entries(vb_root_node);
    }

    //now remove the entries that are written back
    sort_victim_buffer();

    vb_total_entries -= count;
}

victim_buf_entry_t* search_victim_entry(uint64_t addr)
{
    uint64_t tag = find_tag(addr);

    victim_buf_entry_t* node = vb_root_node;
    if(node == NULL) {
        return NULL;
    }

    while(1) {
        if(node->cache_line->tag_addr > tag) {
            if(node->lchild == NULL)
                return NULL;
            else
                node = node->lchild;
        } else if(node->cache_line->tag_addr == tag) {
            return node;
        } else {
            if(node->rchild == NULL)
                return NULL;
            else
                node = node->rchild;
        }
    }
    return NULL;
}

victim_buf_entry_t* proceed_vb_entry(victim_buf_entry_t* node, victim_buf_entry_t* delnode)
{
    if(delnode->lchild == NULL && delnode->rchild == NULL)
        return NULL;
    else if(delnode->rchild == NULL)
        return delnode->lchild;
    else
        return delnode->rchild;
    return NULL;
}

void delete_victim_entry(uint64_t addr)
{
    uint64_t tag = find_tag(addr);
    if(vb_root_node->cache_line->tag_addr == tag) {
        if(vb_root_node->rchild == NULL) {
            if(vb_root_node->lchild == NULL) {
                free(vb_root_node);
                vb_root_node = NULL;
            } else {
                vb_root_node = vb_root_node->lchild;
            }
        } else {
            vb_root_node->rchild->lchild = vb_root_node->lchild;
            vb_root_node = vb_root_node->rchild;
        }
        return;
    }
    victim_buf_entry_t* node = vb_root_node;
    while(1) {
        if(node->cache_line->tag_addr > tag) {
            if(node->lchild == NULL) {
                return;
            } else if(node->lchild->cache_line->tag_addr == tag) {
                node->lchild = proceed_vb_entry(node, node->lchild);
                return;
            } else {
                node = node->lchild;
            }
        } else if(node->cache_line->tag_addr < tag) {
            if(node->rchild == NULL) {
                return;
            } else if(node->rchild->cache_line->tag_addr == tag) {
                node->rchild = proceed_vb_entry(node, node->rchild);
                return;
            } else {
                node = node->rchild;
            }
        }
    }
}

static void traverse_vb(victim_buf_entry_t* node)
{
    if(node == NULL)
        return;

    if(node->cache_line->modified_flag == 0) {
        delete_victim_entry(node->cache_line->tag_addr);
        //start traversing again..
//        traverse_vb(vb_root_node);
//        return;
    }
    //first left child
    traverse_vb(node->lchild);
    //then right child
    traverse_vb(node->rchild);
}

void sort_victim_buffer()
{
    //at now only traverse the buffer
    traverse_vb(vb_root_node);
}

